METHODS OF BASIC NON-MODULAR OPERATIONS
IN MODULAR ARITHMETIC USING INTERVAL POSITIONAL CHARACTERISTICS 

Isupov Konstantin Sergeevich, Postgraduate student, Vyatka State University (36 Moscovskaya street, Kirov, Russia), isupov.k@gmail.com 

004.052

Background. Residue Number Systems (RNS) and modular arithmetic enable independent processing of individual bits of numbers and find their application in many strategically important areas of science, such as cryptography, digital signal processing, high-precision calculations, etc. It is known that the main problem of the efficient use of RNS is the complexity of non-modular operations that require assessement of the positional values of modular numbers. The purpose of the study is a theoretical and scientific grounding of a new method of basic nonmodular operations in modular arithmetic (comparison, sign determination, overflow detection), which is based on the calculation and analysis of interval positional characteristics of modular numbers. This method is characterized by its simplicity and allows to get reliable evaluation of the relative positional magnitude of a modular number asymptotically fast.
Materials and methods. To solve the problem of the effective defenition of the relative positional value of a number represented in the residue number system, the Chinese Remainder Theorem has been used. The reliability of results of non-modular operations is proved by the fundamentals of Interval Analysis.
Results. A new method of the definition of non-modular comparisons in residue number systems, sign determination and overflow detection based on the calculation and analysis of interval characteristics of modular numbers has been suggested. The formal conditions for the correct execution of non-modular operations using the proposed method have been identified. The analysis of the complexity of the interval characteristics calculation has been fulfilled. A probabilistic evaluation for the intersection of interval characteristics of two modular numbers, which leads to the violation of sufficient conditions for the correctness of non-modular operations, has been obtained.
Conclusions. Comparison, sign determination and overflow detection operations in RNS can be reliably performed using the proposed interval positional characteristics evaluation technique in linear time for the sequential computations and logarithmic – in parallel. The proposed method does not require high hardware cost. In some cases, the interval positional characteristics do not enable to determine the result of the non-modular operation. The probability of occurrence of such cases is (n⋅21−k ) (1−n⋅21−k ) , where k is a count of bits to represent the fractional part of boundary interval characteristic, n is count of RNS modules. 

residue number system, non-modular operation, comparison, sign determination, overflow detection, interval positional characteristic, interval analysis. 

1. Akushskiy I. Ya., Yuditskiy D. I. Mashinnaya arifmetika v ostatochnykh klassakh [Machine arithmetic in residue classes]. Moscow: Sov. Radio, 1968, 440 p. 
2. Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation (Advances in Computer Science and Engineering Texts). London: Imperial College Press, 2007, 312 p.
3. Chervyakov N. I., Averbukh V. M., Babenko M. G., Lyakhov P. A., Gladkov A. V., Gapochkin A. V. Fundamental'nye issledovaniya [Fundamental research]. 2012, no. 6 (1), pp. 189–193.
4. Koç Ç. K. Processors of the IEEE International Conference Computer Design (ICCD' 89): VLSI in Computers and Processors. October, 1989, pp. 18–21.
5. Dimauro G., Impedovo S., Pirlo G. IEEE transactions on computers. 1993, vol. 42, no. 5, pp. 608–612.
6. Polisskiy Yu. D. 50 let modulyarnoy arifmetike: yubileynaya Mezhdunar. nauch.-tekhn. konf. [50th anniversary of modular arithmetic: International scientific and practical conference]. Moscow: MIET, 2006, pp. 274–290.
7. Isupov K. S. Fundamental'nye issledovaniya [Fundamental research]. 2013, no. 4 (5), pp. 796–800.
8. Kulish U., Rats D., Khammer R., Khoks M. Dostovernye vychisleniya. Bazovye chislennye metody; per. s angl. [Authentic calculation. Basic numerical methods; translation from English]. Moscow; Izhevsk, 2005, 496 p.
9. Sharyy S. P. Konechnomernyy interval'nyy analiz [Finite-dimensional interval analysis]. 2012, 605 p. Available at: //http: www.nsc.ru/interva/
10. Kaucher E. Computing Supplement. 1989, vol. 2, pp. 33–49.